package SwordFingerOffer;

public class Q53_1_MissNumber {
    //0 - 1缺失的数字
    //一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
    // 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

    //下标定点轮转
    public int missingNumber(int[] nums) {

        if (nums.length == 1 && nums[0] == 0){
            return 1;
        }
        for (int i = 0; i < nums.length; i++) {
            //下标不对应
            while (nums[i] != i){
                if (nums[i] == nums.length){
                    return nums[i] - 1;
                }
                //交换到对应的位置
                if (!swap(nums, i, nums[i])){
                    return nums[i] + 1;
                }
            }
        }
        return 0;
    }

    public boolean swap(int[] nums, int i, int j) {
        if (nums[i] == nums[j]){
            return false;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        return true;
    }

    public static void main(String[] args) {
        Q53_1_MissNumber fun = new Q53_1_MissNumber();
        System.out.println(fun.missingNumber(new int[]{0, 1, 3}));
    }

}
